package offer;
import java.util.Map;

/**
 * @Author Elephas
 * @Date 2022/2/8
 **/
@FunctionalInterface
public interface GridIllumination {
    int[] gridIllumination(int n, int[][] lamps, int[][] queries);
}
class GridIlluminationImpl1 implements GridIllumination{


    static final int DARK = 0;
    @Override
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        int[][] grids = new int[n][n];
        /* grids 的内容若为0，表示改格子位被照亮，
         * 若 grid = count > 0，表示此处无灯，被照亮 count 次
         * 若 grid = count < 0，表示此处有灯，被照亮 -count 次
         */
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grids[i][j] = DARK;
            }
        }
        for(int[] lamp : lamps){
            int x = lamp[0];
            int y = lamp[1];
            if(grids[x][y] == DARK) {
                grids[x][y] = -1;
            }else if(grids[x][y] > 0){
                grids[x][y]++;
                grids[x][y] = -grids[x][y];
            }else{
                grids[x][y]--;
            }
            // illuminate row x
            for (int j = 0; j < n; j++) {
                if(j != y) {
                    if (grids[x][j] >= 0) {
                        grids[x][j]++;
                    } else {
                        grids[x][j]--;
                    }
                }
            }
            // illuminate column y
            for (int i = 0; i < n; i++) {
                if(i != x) {
                    if (grids[i][y] >= 0) {
                        grids[i][y]++;
                    } else {
                        grids[i][y]--;
                    }
                }
            }
            // illuminate diagonal
            for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) {
                if(grids[i][j] >= 0){
                    grids[i][j]++;
                }else {
                    grids[i][j]--;
                }
            }
            for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
                if(grids[i][j] >= 0){
                    grids[i][j]++;
                }else {
                    grids[i][j]--;
                }
            }
        }
        int queryLen = queries.length;
        int[] ans = new int[queryLen];
        for (int k = 0; k < queryLen; k++) {
            int[] query = queries[k];
            int x = query[0];
            int y = query[1];
            if(grids[x][y] != DARK){
                ans[k] = 1;
            }else{
                ans[k] = 0;
            }
            // turn off adjacent
            for (int i = -1; i < 2; i++) {
                for (int j = -1; j < 2; j++) {
                    int neighborX = x + i;
                    int neighborY = y + j;
                    if(neighborX >= 0 && neighborY >= 0 && neighborX < n && neighborY < n){
                        if(grids[neighborX][neighborY] < 0){
                            grids[neighborX][neighborY]++;
                            grids[neighborX][neighborY] = -grids[neighborX][neighborY];
                            for (int row = 0; row < n; row++) {
                                if(row != neighborX) {
                                    if (grids[row][neighborY] >= 0) {
                                        grids[row][neighborY]--;
                                    } else {
                                        grids[row][neighborY]++;
                                    }
                                }
                            }
                            for (int column = 0; column < n; column++) {
                                if(column != neighborY){
                                    if(grids[neighborX][column] >= 0){
                                        grids[neighborX][column]--;
                                    }else{
                                        grids[neighborX][column]++;
                                    }
                                }
                            }
                            for(int row = neighborX - 1, column = neighborY - 1;
                                row >= 0 && column >= 0;
                                row--, column--){
                                if(grids[row][column] >= 0){
                                    grids[row][column]--;
                                }else{
                                    grids[row][column]++;
                                }
                            }
                            for(int row = neighborX + 1, column = neighborY + 1;
                                row < n && column < n;
                                row++, column++){
                                if(grids[row][column] >= 0){
                                    grids[row][column]--;
                                }else{
                                    grids[row][column]++;
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
}
class GridIlluminationImpl2 implements GridIllumination{
    public static void main(String[] args) {
        //new GridIlluminationImpl2().gridIllumination(5,new int[][]{{0,0},{4,4}},new int[][]{{0, 4},{0,1},{1,4}});
       /*
        new GridIlluminationImpl2().gridIllumination(6,
                new int[][]{{2,5}, {4,2},{0,3}, {0,5},{1,4},{4,2},{3,3},{1,0}},
                new int[][]{{4,3},{3,1},{5,3},{0,5},{4,4},{3,3}});


        */
        new GridIlluminationImpl2().gridIllumination(6,
                new int[][]{{2,5}, {4,2},{0,3}, {0,5},{1,4},{4,2},{3,3},{1,0}},
                new int[][]{{2,5}, {4,2},{0,3}, {0,5},{1,4},{4,2},{3,3},{1,0}});

        new GridIlluminationImpl2().gridIllumination(6,
                new int[][]{{0,2},{1,1},{2,0}},
                new int[][]{{0,2},{1,1},{2,0}});
    }

    /**
     * o(n), o(n^2),
     * 使用一个二维数组来模拟灯的照射情况，当给定数据 n > 10000 时，会发生内存不足
     * @param n
     * @param lamps
     * @param queries
     * @return
     */

    @Override

    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        byte[][] grids = new byte[n][n];
        int[] ans = new int[queries.length];
        initGrids(grids,n,lamps,queries,ans);
        processQueries(grids,n,lamps,queries,ans);
        return ans;
    }
    private void initGrids(byte[][] grids, int n, int[][] lamps, int[][] queries, int[] ans){
        for(int[] lamp : lamps){
            int x = lamp[0];
            int y = lamp[1];
            if(grids[x][y] >= 0) {
                illuminate(true, x, y,grids,n,lamps,queries,ans);
            }
        }
    }
    private void processQueries(byte[][] grids, int n, int[][] lamps, int[][] queries, int[] ans){
        int count = 0;
        for(int[] query : queries){
            int x = query[0];
            int y = query[1];
            if(grids[x][y] == 0){
                ans[count++] = 0;
            }else{
                ans[count++] = 1;
            }
            // turn off the lamp if it exists
            for(int deltaX = -1; deltaX < 2; deltaX++){
                for(int deltaY = -1; deltaY < 2; deltaY++){
                    int newPosX = x + deltaX;
                    int newPosY = y + deltaY;
                    if(newPosX >= 0 && newPosX < n && newPosY >= 0 && newPosY < n) {
                        if (grids[newPosX][newPosY] < 0) {
                            illuminate(false,newPosX,newPosY,grids,n,lamps,queries,ans);
                        }
                    }
                }
            }
        }
    }
    private void illuminate(boolean isIlluminate, int x, int y,byte[][] grids, int n, int[][] lamps, int[][] queries, int[] ans){
        int delta = isIlluminate? 1 : -1;
        if(isIlluminate){
            if(grids[x][y] > 0){
                grids[x][y] = (byte) - (grids[x][y] + 1);
            }else{
                grids[x][y]--;
            }
        }else{
            grids[x][y] = (byte) -(grids[x][y] + 1);
        }

        // illuminate row x
        for(int row = 0; row < n; row++){
            if(row != x){
                if(grids[row][y] >= 0){
                    grids[row][y]+=delta;
                }else{
                    grids[row][y]-=delta;
                }
            }
        }
        // illuminate column y
        for (int column = 0; column < n; column++) {
            if(column != y){
                if(grids[x][column] >= 0){
                    grids[x][column]+=delta;
                }else{
                    grids[x][column]-=delta;
                }
            }
        }
        // illuminate diagonal
        for(int row = x - 1, column = y - 1; row >= 0 && column >= 0; row--, column--){
            if(grids[row][column] >= 0){
                grids[row][column]+=delta;
            }else{
                grids[row][column]-=delta;
            }
        }
        for(int row = x + 1, column = y + 1; row < n && column < n; row++, column++){
            if(grids[row][column] >= 0){
                grids[row][column]+=delta;
            }else{
                grids[row][column]-=delta;
            }
        }
        for(int row = x - 1, column = y + 1; row < n && column < n && row >= 0 && column >= 0; row--, column++){
            if(grids[row][column] >= 0){
                grids[row][column]+=delta;
            }else{
                grids[row][column]-=delta;
            }
        }
        for(int row = x + 1, column = y - 1; row < n && column < n && row >= 0 && column >= 0; row++, column--){
            if(grids[row][column] >= 0){
                grids[row][column]+=delta;
            }else{
                grids[row][column]-=delta;
            }
        }
    }
}
class GridIlluminationImpl3 implements GridIllumination {
    @Override
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        return new int[0];
    }

    /**
     * 抄代码，哈希表，
     * @param n
     * @param lamps
     * @param queries
     * @return
     */

    /*
    @Override
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Map<Integer,Integer> row = new HashMap();
        Map<Integer,Integer> column = new HashMap();
        Map<Integer,Integer> diagonal = new HashMap();
        Map<Integer,Integer> antiDiagonal = new HashMap();
        Set<Long> points = new HahsSet();
        for(int[] lamp : lamps){
            int x = lamp[0];
            int y = lamp[1];
            int xMinusY = x - y;
            int xPlusY = x + y;
            if(!points.add(hash(x,y))){
                continue;
            }
            row.put(x,row.getOrDefault(x,0) + 1);
            column.put(y,column.getOrDefault(y,0) + 1);
            diagonal.put(xMinusY,diagonal.getOrDefault(xMinusY, 0) + 1);
            antiDiagonal.put(xPlusY, diagonal.getOrDefault(xPlusY, 0) + 1);
        }
        int[] ans = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            int x = queries[i][0], y = queries[i][1];
            int xMinusY = x - y;
            int xPlusY = x + y;
            if(row.getOrDefault(x,0) > 0 ||
                column.getOrDefault(y,0) > 0 ||
                    diagonal.getOrDefault(x,0) > 0 ||
                        antiDiagonal.getOrDefault(x,0) > 0)
                ans[i] = 1;
            }

        }
        return ans;
    }
    private long hash(int x, int y) {
        return (long) x + ((long) y << 32);
    }


     */
}